package com.salim.leetcode.$144;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class BinaryTreePreorderTraversal {
    //树的先序遍历-> 根 左 右 要求使用迭代
    //先一直入栈左 并记录结果
    //如果碰到节点左右都没有 回退到有右节点的根 pop掉根 push进右节点
    //重复

    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current;
        List<Integer> result = new ArrayList<>();
        if(root==null){
            return result;
        }
        stack.push(root);
        while (!stack.isEmpty()){
            current = stack.peek();
            if(current.left!=null){
                stack.push(current.left);
                result.add(current.val);
            }else if(current.right!=null){
                stack.pop();
                stack.push(current.right);
                result.add(current.val);
            }else{
                result.add(current.val);
                //回退到有右节点的节点 pop自身 push右节点
                while(!stack.isEmpty()&& stack.peek().left==null && stack.peek().right==null){
                    stack.pop();
                    if(!stack.isEmpty()){
                        stack.peek().left = null;
                    }
                }
                if(!stack.isEmpty() && stack.peek().right!=null){
                    current = stack.pop();
                    stack.push(current.right);
                }
            }
        }
        return result;
    }

    //[3,1,2]
    //[3,1,null,null,2]

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
